We consider the problem of planning trajectories for a group of $N$ vehicles,each aiming to reach its own target set while avoiding danger zones of othervehicles. The analysis of problems like this is extremely importantpractically, especially given the growing interest in utilizing unmannedaircraft systems for civil purposes. The direct solution of this problem bysolving a single-obstacle Hamilton-Jacobi-Isaacs (HJI) variational inequality(VI) is numerically intractable due to the exponential scaling of computationcomplexity with problem dimensionality. Furthermore, the single-obstacle HJI VIcannot directly handle situations in which vehicles do not have a commonscheduled arrival time. Instead, we perform sequential path planning byconsidering vehicles in order of priority, modeling higher-priority vehicles astime-varying obstacles for lower-priority vehicles. To do this, we solve adouble-obstacle HJI VI which allows us to obtain the reach-avoid set, definedas the set of states from which a vehicle can reach its target while stayingwithin a time-varying state constraint set. From the solution of thedouble-obstacle HJI VI, we can also extract the latest start time and theoptimal control for each vehicle. This is a first application of thedouble-obstacle HJI VI which can handle systems with time-varying dynamics,target sets, and state constraint sets, and results in computation complexitythat scales linearly, as opposed to exponentially, with the number of vehiclesin consideration.
展开▼
